#include <iostream>
#include <algorithm> // 用于 std::fill

#define MAX_NODE_NUM 10000
#define MAX_EDGE_NUM 10000

// 点信息，节点的边信息，数组式的链表
int g_nNodeNum;                      // 节点总数
int g_nNodeEdge[MAX_NODE_NUM];       // 每个节点的第一条边的编号

// 当前边编号，只和构图时输入顺序相关
int g_nEdgeNum;                      // 当前边的编号
int g_nEdgeTo[MAX_EDGE_NUM];         // 边的目标节点
int g_nEdgeNextAdj[MAX_EDGE_NUM];    // 下一条邻接边的编号
int g_nEdgeWeight[MAX_EDGE_NUM];     // 边的权重

// 初始化图
void InitializeGraph() {
    g_nNodeNum = 0;
    g_nEdgeNum = 0;
    std::fill(g_nNodeEdge, g_nNodeEdge + MAX_NODE_NUM, -1); // 初始化链表头为 -1
}

// 添加有向边到邻接表
void AddEdge(int nNodeFrom, int nNodeTo, int nWeight) {
    // 添加从 nNodeFrom 到 nNodeTo 的边
    g_nEdgeTo[++g_nEdgeNum] = nNodeTo;
    g_nEdgeWeight[g_nEdgeNum] = nWeight;
    g_nEdgeNextAdj[g_nEdgeNum] = g_nNodeEdge[nNodeFrom];
    g_nNodeEdge[nNodeFrom] = g_nEdgeNum;
}

// 打印图的邻接表
void PrintGraph() {
    for (int i = 0; i < g_nNodeNum; i++) {
        std::cout << "Node " << i << " -> ";
        for (int e = g_nNodeEdge[i]; e != -1; e = g_nEdgeNextAdj[e]) {
            std::cout << "(" << g_nEdgeTo[e] << ", " << g_nEdgeWeight[e] << ") ";
        }
        std::cout << std::endl;
    }
}

int main() {
    // 初始化图
    InitializeGraph();

    // 设置节点总数
    g_nNodeNum = 5;

    // 添加有向边
    AddEdge(0, 1, 10);
    AddEdge(0, 2, 20);
    AddEdge(1, 3, 30);
    AddEdge(2, 4, 40);
    AddEdge(3, 4, 50);

    // 打印邻接表
    std::cout << "Directed Graph:" << std::endl;
    PrintGraph();

    // 重置图
    InitializeGraph();
    g_nNodeNum = 5;

    // 添加无向边（通过调用两次 AddEdge）
    AddEdge(0, 1, 10); AddEdge(1, 0, 10);
    AddEdge(0, 2, 20); AddEdge(2, 0, 20);
    AddEdge(1, 3, 30); AddEdge(3, 1, 30);
    AddEdge(2, 4, 40); AddEdge(4, 2, 40);
    AddEdge(3, 4, 50); AddEdge(4, 3, 50);

    // 打印邻接表
    std::cout << "Undirected Graph:" << std::endl;
    PrintGraph();

    return 0;
}